package com.sicheng.lc.周赛.分类.dp.路径;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/12 16:24
 */
public class 网格中的最小路径代价 {
    //    https://leetcode.cn/problems/minimum-path-cost-in-a-grid/
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        int res = Integer.MAX_VALUE;
        System.arraycopy(grid[0], 0, dp[0], 0, n);
        for (int i = 1; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE >> 2);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + grid[i][j] + moveCost[grid[i - 1][k]][j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[m - 1][i]);
        }
        return res;
    }
}
